// 内存管理

#include "types.h"
extern void printk(char *fmt, ...);

#define MEMORY_END_VIRTUAL_ADDR 0x30700000
#define MEMORY_START_VIRTUAL_ADDR 0x300f0000
// 待管理空间,6356992字节
#define MEMORY_BYTES (MEMORY_END_VIRTUAL_ADDR - MEMORY_START_VIRTUAL_ADDR)

// 页表大小4k字节
#define MEMORY_PAGE_BYTES (4 * 1024)

#define MEMORY_PAGE_FLAG_IDLE 0x0
#define MEMORY_PAGE_FLAG_BUSY 0x1
#define MEMORY_PAGE_FLAG_DIRTY 0x2
// 页表描述体
struct memory_page
{
    unsigned int vAddr;
    unsigned int flag;
    struct memory_page *pNextPage;
};
// 页表描述体大小
#define MEMORY_PAGE_DESCRIPTOR_BYTES (sizeof(struct memory_page))
// 页表描述体起始虚拟地址
#define MEMORY_PAGE_DESCRIPTOR_START_VIRTUAL_ADDR MEMORY_START_VIRTUAL_ADDR

// 页表总个数,6356992/(4*1024+12)=1547
#define MEMORY_PAGE_NUM ((MEMORY_END_VIRTUAL_ADDR - MEMORY_START_VIRTUAL_ADDR) / (MEMORY_PAGE_BYTES + MEMORY_PAGE_DESCRIPTOR_BYTES))
// 页表起始地址
#define MEMORY_PAGE_START_VIRTUAL_ADDR (MEMORY_START_VIRTUAL_ADDR + MEMORY_PAGE_DESCRIPTOR_BYTES * MEMORY_PAGE_NUM)

#define MEMORY_BUDDY_TYPE_64K (64 * 1024)
#define MEMORY_BUDDY_TYPE_128K (128 * 1024)
#define MEMORY_BUDDY_TYPE_256K (256 * 1024)
#define MEMORY_BUDDY_TYPE_512K (512 * 1024)
#define MEMORY_BUDDY_TYPE_1024K (1024 * 1024)
#define MEMORY_BUDDY_TYPE_NUM 5
#define MEMORY_IS_BUDDY_TYPE(type) (    \
    (type == MEMORY_BUDDY_TYPE_64K) ||  \
    (type == MEMORY_BUDDY_TYPE_128K) || \
    (type == MEMORY_BUDDY_TYPE_256K) || \
    (type == MEMORY_BUDDY_TYPE_512K) || \
    (type == MEMORY_BUDDY_TYPE_1024K))

// buddy描述体
struct memory_buddy
{
    unsigned int type;
    unsigned int num;
    struct memory_page *pFirstPage;
};
// buddy池
static struct memory_buddy buddy[MEMORY_BUDDY_TYPE_NUM];

static inline void memory_init_all_page(void)
{
    unsigned int i = 0;
    struct memory_page *pPage = NULL;
    for (i = 0; i < MEMORY_PAGE_NUM; i++)
    {
        pPage = (struct memory_page *)MEMORY_PAGE_DESCRIPTOR_START_VIRTUAL_ADDR + i;
        pPage->vAddr = MEMORY_PAGE_START_VIRTUAL_ADDR + i * MEMORY_PAGE_BYTES;
        pPage->flag = MEMORY_PAGE_FLAG_IDLE;
        pPage->pNextPage = NULL;
        // printk("i:%a,vAddr:%a\n",i,pPage->vAddr);
    }
}

static inline void memory_init_all_buddy(void)
{
    unsigned int i = 0;
    struct memory_page *pPage = NULL;

    buddy[0].type = MEMORY_BUDDY_TYPE_64K;
    buddy[0].num = 0;
    buddy[0].pFirstPage = NULL;

    buddy[1].type = MEMORY_BUDDY_TYPE_128K;
    buddy[1].num = 0;
    buddy[1].pFirstPage = NULL;

    buddy[2].type = MEMORY_BUDDY_TYPE_256K;
    buddy[2].num = 0;
    buddy[2].pFirstPage = NULL;

    buddy[3].type = MEMORY_BUDDY_TYPE_512K;
    buddy[3].num = 0;
    buddy[3].pFirstPage = NULL;

    // 1547个4k的page可生成6个1024k的buddy
    // 6个1024k的buddy利用了1536个4k的page
    buddy[4].type = MEMORY_BUDDY_TYPE_1024K;
    buddy[4].num = 6;
    buddy[4].pFirstPage = (struct memory_page *)MEMORY_PAGE_DESCRIPTOR_START_VIRTUAL_ADDR;
    pPage = buddy[4].pFirstPage;
    for (i = 0; i < buddy[4].num * (buddy[4].type / MEMORY_PAGE_BYTES); i++)
    {
        // printk("i:%a,page vAddr:%a\n",i,pPage->vAddr);
        pPage->flag = MEMORY_PAGE_FLAG_BUSY;
        if (i == buddy[4].num * (buddy[4].type / MEMORY_PAGE_BYTES) - 1)
        {
            pPage->pNextPage = NULL;
        }
        else
        {
            pPage->pNextPage = pPage + 1;
            pPage = pPage->pNextPage;
        }
    }
}

// 分配指定的buddy
static inline struct memory_page *memory_malloc_buddy_p(struct memory_buddy *buddyAddr)
{
    if (buddyAddr == NULL)
    {
        return (NULL);
    }

    struct memory_page *pPage = NULL;
    struct memory_buddy *pBuddy = buddyAddr;

    // 无指定的buddy
    if (pBuddy->num < 1)
    {
        return (NULL);
    }
    // 有一个指定的buddy
    else if (pBuddy->num == 1)
    {
        pPage = pBuddy->pFirstPage;
        for (;;)
        {
            if (pPage == NULL)
            {
                break;
            }
            pPage->flag = MEMORY_PAGE_FLAG_DIRTY;
            pPage = pPage->pNextPage;
        }
        pPage = pBuddy->pFirstPage;
        pBuddy->pFirstPage = NULL;
        pBuddy->num = 0;
        return (pPage);
    }
    // 有多个指定的buddy
    else if (pBuddy->num > 1)
    {
        pPage = (pBuddy->pFirstPage) + (pBuddy->num - 1) * (pBuddy->type / MEMORY_PAGE_BYTES) - 1;
        pPage->pNextPage = NULL;
        pPage = (pBuddy->pFirstPage) + (pBuddy->num - 1) * (pBuddy->type / MEMORY_PAGE_BYTES);
        for (;;)
        {
            if (pPage == NULL)
            {
                break;
            }
            pPage->flag = MEMORY_PAGE_FLAG_DIRTY;
            pPage = pPage->pNextPage;
        }
        pPage = (pBuddy->pFirstPage) + (pBuddy->num - 1) * (pBuddy->type / MEMORY_PAGE_BYTES);
        pBuddy->num--;
        return (pPage);
    }
}
static inline struct memory_page *memory_malloc_buddy_recurse(struct memory_buddy *buddyAddr)
{
    if (buddyAddr == NULL)
    {
        return (NULL);
    }

    struct memory_page *pFirstPage = NULL;
    struct memory_buddy *pBuddy = buddyAddr;

    // 若当前大小的buddy个数大于1
    if (pBuddy->num >= 1)
    {
        pFirstPage = memory_malloc_buddy_p(pBuddy);
        return (pFirstPage);
    }
    // 若当前大小的buddy个数等于0
    else if (pBuddy->num == 0)
    {
        // 递归分配大小高一级的buddy
        pFirstPage = memory_malloc_buddy_recurse(pBuddy + 1);
        // 分配大小高一级的buddy失败
        if (pFirstPage == NULL)
        {
            return (NULL);
        }
        // 分配大小高一级的buddy成功
        else
        {
            pBuddy->pFirstPage = pFirstPage;
            pBuddy->num = (pBuddy->num) + 2;
            pFirstPage = memory_malloc_buddy_p(pBuddy);
            return (pFirstPage);
        }
    }
}
static inline struct memory_page *memory_malloc_buddy(unsigned int type)
{
    struct memory_page *pHeadPage = NULL;
    switch (type)
    {
    case MEMORY_BUDDY_TYPE_64K:
        pHeadPage = memory_malloc_buddy_recurse(&buddy[0]);
        break;
    case MEMORY_BUDDY_TYPE_128K:
        pHeadPage = memory_malloc_buddy_recurse(&buddy[1]);
        break;
    case MEMORY_BUDDY_TYPE_256K:
        pHeadPage = memory_malloc_buddy_recurse(&buddy[2]);
        break;
    case MEMORY_BUDDY_TYPE_512K:
        pHeadPage = memory_malloc_buddy_recurse(&buddy[3]);
        break;
    case MEMORY_BUDDY_TYPE_1024K:
        pHeadPage = memory_malloc_buddy_recurse(&buddy[4]);
        break;
    default:
        break;
    }
    return (pHeadPage);
}
// 获取由pFirstPage指定的buddy的大小类型
static inline unsigned int memory_get_buddy_type(struct memory_page *pFirstPage)
{
    if (pFirstPage == NULL)
    {
        return (0);
    }
    if (((pFirstPage + (MEMORY_BUDDY_TYPE_64K / MEMORY_PAGE_BYTES) - 1)->pNextPage) == NULL)
    {
        return (MEMORY_BUDDY_TYPE_64K);
    }
    if (((pFirstPage + (MEMORY_BUDDY_TYPE_128K / MEMORY_PAGE_BYTES) - 1)->pNextPage) == NULL)
    {
        return (MEMORY_BUDDY_TYPE_128K);
    }
    if (((pFirstPage + (MEMORY_BUDDY_TYPE_256K / MEMORY_PAGE_BYTES) - 1)->pNextPage) == NULL)
    {
        return (MEMORY_BUDDY_TYPE_256K);
    }
    if (((pFirstPage + (MEMORY_BUDDY_TYPE_512K / MEMORY_PAGE_BYTES) - 1)->pNextPage) == NULL)
    {
        return (MEMORY_BUDDY_TYPE_512K);
    }
    if (((pFirstPage + (MEMORY_BUDDY_TYPE_1024K / MEMORY_PAGE_BYTES) - 1)->pNextPage) == NULL)
    {
        return (MEMORY_BUDDY_TYPE_1024K);
    }
}
// 将由pFirstPage指定的buddy追加到pBuddy尾部
static inline void memory_append_buddy(struct memory_buddy *pBuddy, struct memory_page *pFirstPage)
{
    if ((pBuddy == NULL) || (pFirstPage == NULL))
    {
        return;
    }
    if (pBuddy->num == 0)
    {
        pBuddy->pFirstPage = pFirstPage;
        pBuddy->num++;
    }
    else if (pBuddy->num > 0)
    {
        (pBuddy->pFirstPage + ((pBuddy->num) * (pBuddy->type) / MEMORY_PAGE_BYTES - 1))->pNextPage = pFirstPage;
        pBuddy->num++;
    }
}
// 释放由pFirstPage指定的buddy
static inline void memory_free_buddy(struct memory_page *pFirstPage)
{
    if (pFirstPage == NULL)
    {
        return;
    }
    struct memory_page *pTmpPage = pFirstPage;
    unsigned int buddyType = memory_get_buddy_type(pFirstPage);
    if (!MEMORY_IS_BUDDY_TYPE(buddyType))
    {
        return;
    }
    // 设置每个待释放的page的flag
    for (;;)
    {
        if (pTmpPage == NULL)
        {
            break;
        }
        pTmpPage->flag = MEMORY_PAGE_FLAG_BUSY;
        pTmpPage = pTmpPage->pNextPage;
    }

    // 将待释放的page加到对应的buddy尾部
    if (buddyType == MEMORY_BUDDY_TYPE_64K)
    {
        memory_append_buddy(&buddy[0], pFirstPage);
    }
    else if (buddyType == MEMORY_BUDDY_TYPE_128K)
    {
        memory_append_buddy(&buddy[1], pFirstPage);
    }
    else if (buddyType == MEMORY_BUDDY_TYPE_256K)
    {
        memory_append_buddy(&buddy[2], pFirstPage);
    }
    else if (buddyType == MEMORY_BUDDY_TYPE_512K)
    {
        memory_append_buddy(&buddy[3], pFirstPage);
    }
    else if (buddyType == MEMORY_BUDDY_TYPE_1024K)
    {
        memory_append_buddy(&buddy[4], pFirstPage);
    }

    // 较小的两块buddy合并为一块较大的buddy
    unsigned int i = 0;
    for (i = 0; i < MEMORY_BUDDY_TYPE_NUM - 1; i++)
    {
        if (buddy[i].num == 2)
        {
            pTmpPage = buddy[i].pFirstPage;
            buddy[i].pFirstPage = NULL;
            buddy[i].num = 0;
            memory_append_buddy(&buddy[i + 1], pTmpPage);
        }
    }
}

static inline void memory_print_buddy(void)
{
    int i = 0;
    for (i = 0; i < MEMORY_BUDDY_TYPE_NUM; i++)
    {
        printk("type:%a,num:%a\n", buddy[i].type, buddy[i].num);
    }
}

// 由指定字节数分配buddy,实际返回构成该buddy的第一个page的虚拟地址
void *memory_malloc(unsigned int bytes)
{
    struct memory_page *pPage = NULL;
    if ((bytes > 0) && (bytes <= MEMORY_BUDDY_TYPE_64K))
    {
        pPage = memory_malloc_buddy(MEMORY_BUDDY_TYPE_64K);
        return ((void *)(pPage->vAddr));
    }
    else if ((bytes > MEMORY_BUDDY_TYPE_64K) && (bytes <= MEMORY_BUDDY_TYPE_128K))
    {
        pPage = memory_malloc_buddy(MEMORY_BUDDY_TYPE_128K);
        return ((void *)(pPage->vAddr));
    }
    else if ((bytes > MEMORY_BUDDY_TYPE_128K) && (bytes <= MEMORY_BUDDY_TYPE_256K))
    {
        pPage = memory_malloc_buddy(MEMORY_BUDDY_TYPE_256K);
        return ((void *)(pPage->vAddr));
    }
    else if ((bytes > MEMORY_BUDDY_TYPE_256K) && (bytes <= MEMORY_BUDDY_TYPE_512K))
    {
        pPage = memory_malloc_buddy(MEMORY_BUDDY_TYPE_512K);
        return ((void *)(pPage->vAddr));
    }
    else if ((bytes > MEMORY_BUDDY_TYPE_512K) && (bytes <= MEMORY_BUDDY_TYPE_1024K))
    {
        pPage = memory_malloc_buddy(MEMORY_BUDDY_TYPE_1024K);
        return ((void *)(pPage->vAddr));
    }
    else
    {
        return (NULL);
    }
}

// 根据page的虚拟地址释放buddy
void memory_free(void *vAddr)
{
    // page的虚拟地址
    unsigned int pageAddr = (unsigned int)vAddr;
    // 对应的首个page描述体地址
    struct memory_page *pPage;
    unsigned int i = 0;
    for (i = 0; i < MEMORY_PAGE_NUM; i++)
    {
        pPage = (struct memory_page *)MEMORY_PAGE_DESCRIPTOR_START_VIRTUAL_ADDR + i;
        if (pPage->vAddr == pageAddr)
        {
            break;
        }
    }
    memory_free_buddy(pPage);
}

void memory_init(void)
{
    memory_init_all_page();
    memory_init_all_buddy();
}

void memory_test(void)
{
    // printk("MEMORY_PAGE_NUM:%a\n",MEMORY_PAGE_NUM);

    memory_init();
    memory_print_buddy();
    struct memory_page *pPage1 = NULL;
    pPage1 = memory_malloc_buddy(MEMORY_BUDDY_TYPE_1024K);
    memory_print_buddy();

    struct memory_page *pPage2 = NULL;
    pPage2 = memory_malloc_buddy(MEMORY_BUDDY_TYPE_64K);
    memory_print_buddy();

    struct memory_page *pPage3 = NULL;
    pPage3 = memory_malloc_buddy(MEMORY_BUDDY_TYPE_256K);
    memory_print_buddy();

    struct memory_page *pPage4 = NULL;
    pPage4 = memory_malloc_buddy(MEMORY_BUDDY_TYPE_256K);
    memory_print_buddy();

    char *p1 = (char *)memory_malloc(100 * 1024);
    if (p1 == NULL)
    {
        printk("memory_malloc return NULL\n");
        return;
    }
    memory_print_buddy();
    memory_free(p1);
    memory_print_buddy();
}